package NewCoder;

import java.util.ArrayList;
import java.util.Arrays;

public class BM54 {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res =new ArrayList<>();
        if(num==null ||num.length<2) return res;
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            if(num[i]>0) return res;
            if(i>0 && num[i-1]==num[i]) continue;
            int L=i+1;
            int R=num.length-1;
            while(L<R){
                int tmp=num[i]+num[L]+num[R];
                if(tmp==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[L]);
                    list.add(num[R]);
                    res.add(list);
                    while(L<R && num[L]==num[L+1]){
                        L++;
                    }
                    while(L<R && num[R]==num[R-1]){
                        R--;
                    }
                    L++;
                    R--;
                }else if(tmp>0){
                    R--;
                }else{
                    L++;
                }
            }
        }
        return res;
    }
}
